package com.company.ljh.easy;

/**
 *338.比特位计数
 * 给你一个整数 n ，对于 0 <= i <= n 中的每个 i ，计算其二进制表示中 1 的个数 ，返回一个长度为 n + 1 的数组 ans 作为答案。
 */
public class 比特位计数 {
    public static  int[] countBits(int n) {
        int result[]=new int[n+1];
        for (int i = 0; i < n+1; i++) {
            int index =i;
            int number = 0;
            while (index!=0){
                if ((index&1) == 1){
                    number++;
                }
                index = index>>1;
            }
            result[i] = number;
        }
        return result;
    }
    /**
     * 动态规划，最高有效位,x为离i最近的2的n次方数
     bits[i]=bits[i-x]+1
     0 1 (2)
     0 1 1 2 (4)
     0 1 1 2 1 2 2 3 (8)
     */
    public static  int[] countBits2(int n) {
        int result[]=new int[n+1];
        //获取当前最近2^n次方数
        int yxw = 0;
        for (int i = 1; i < n+1; i++) {
            //当且仅当i&(i-1) = 0时,n为2的x次方数
           if ((i&(i-1)) == 0){
               yxw = i;
           }
           result[i] = result[i-yxw]+1;
        }
        return result;
    }
    public static void main(String[] args) {
        int[] ints = countBits2(5);
        System.out.println(ints);
    }
}
